package com.zhangxiaofanfan.hotcode.first;

import java.util.Arrays;

/**
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode085 {
    public static void main(String[] args) {
        HotCode085 hotCode = new HotCode085();
        int[] coins = {1, 2, 5};
        System.out.println(hotCode.coinChange(coins, 11));
    }

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        Arrays.sort(coins);
        if (amount < coins[0]) {
            return -1;
        }
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0, coinCount, frontIndex; i < coins.length; i++) {
            for (int j = 1; j < dp.length; j++) {
                coinCount = j / coins[i];
                while (coinCount > 0) {
                    frontIndex = j - coins[i] * coinCount;
                    dp[j] = Math.min(dp[j], dp[frontIndex] == Integer.MAX_VALUE ? Integer.MAX_VALUE : dp[frontIndex] + coinCount);
                    coinCount--;
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}